# -*- coding: utf-8 -*-            
# @Time : 2022/11/28 22:16
# @Author  : lining
# @FileName: 冒泡和插入排序的比较.py
"""
冒泡排序不管怎么优化，元素交换的次数是一个固定值，是原始数据的逆序度。插入排序是同样的，不管怎么优化，元素移动的次数也等于原始数据的逆序度。
但是，从代码实现上来看，冒泡排序的数据交换要比插入排序的数据移动要复杂，冒泡排序需要 3 个赋值操作，而插入排序只需要 1 个。
冒泡：两两交换
a,b = b,a
插入：把这个值另外保存起来，把前面的元素后移一位
"""
import time
import random


class BubbleSort():
    def bubblesort(self, data, num):
        # 优化：如果这一轮没有交换过数据就代表剩下的数据已经有序，就直接退出
        change = True
        len_data = len(data)
        for i in range(len_data):
            for y in range(i+1, len_data):
                if data[i]<data[y]:
                    data[y], data[i] = data[i], data[y]
                    change = False
            if change:
                break
        print(f'冒泡排序第{num}组完成')


class InsertSort():
    def insertsort(self, data_list, num):
        len_data = len(data_list)
        for i in range(1, len_data):
            a = data_list[i]
            for x in range(i-1, -1, -1):
                if a < data_list[x]:
                    data_list[x+1] = data_list[x]
                if x == 0 or a > data_list[x]:
                    data_list[x] = a
                    break
        print(f'插入排序第{num}组完成')


# 随机生成个数位200的列表
# a = [list(random.sample([x for x in range(1, 201)], 200)) for i in range(10000)]
# with open('1.txt', 'w') as file:
#     file.write(str(a))
with open('1.txt', 'r') as file:
    a = list(file.read())
start_time = time.perf_counter()
for i in range(10000):
    # BubbleSort().bubblesort(a[i], i)
    InsertSort().insertsort(a[i], i)
end_time = time.perf_counter()
print(end_time-start_time)